#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //error
    int ans1(int k, vector<int>& prices){
        int ret = 0;
        if(prices.size() <= 1){
            return 0;
        }
        for(int i = 0; i != k; i++){
            pair<int, pair<int, int>> temp = maxProfit(prices);
            ret = ret + temp.first;
            pair<int, int> index = temp.second;
            prices.erase(prices.begin() + index.first);
            prices.erase(prices.begin() + index.second-1);
            if(prices.size() < 2){
                break;
            }
        }
        return ret;
    }

    pair<int, pair<int, int>> maxProfit(vector<int>& prices){
        int minprice = INT32_MAX, maxprice = 0;
        int max_num, min_num;
        pair<int, int> index;
        for(int i = 0; i != prices.size(); i++){
            maxprice = max(maxprice, prices[i] - minprice);
            if(maxprice == prices[i] - minprice){
                max_num = prices[i];
                min_num = minprice;
            }
            minprice = min(prices[i], minprice);
        }
        for(int i = 0; i != prices.size(); i++){
            if(prices[i] == min_num){
                index.first = i;
            }
            if(prices[i] == max_num){
                index.second = i;
            }
        }

        return {maxprice, index};
    }

    int ans2(int k, vector<int>& prices){
        if(prices.empty()){
            return 0;
        }

        int len = prices.size();
        k = min(k, len/2);
        vector<int> buy(k+1, INT32_MIN/2);
        vector<int> sell(k+1, INT32_MIN/2);

        buy[0] = -prices[0];
        sell[0] = 0;

        for(int i = 1; i != len; i++){
            buy[0] = max(buy[0], sell[0] - prices[i]);
            for(int j = 1; j != k+1; j++){
                buy[j] = max(buy[j], sell[j] - prices[i]);
                sell[j] = max(sell[j], buy[j-1] + prices[i]);
            }
        }

        return *max_element(sell.begin(), sell.end());

    }

};

void test1(){
    Solution s;
    vector<int> prices = {2,4,1};
    int k = 2;

    int ret = s.ans2(k, prices);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> prices = {3,2,6,5,0,3};
    int k = 1;

    int ret = s.ans2(k, prices);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<int> prices = {6,1,3,2,4,7};
    int k = 2;

    int ret = s.ans2(k, prices);
    cout << ret << endl;
}


int main(void){
    test1();
    test2();
    test3();

    return 0;
}